package 前缀和;

import java.util.HashMap;
import java.util.Map;

public class 和可被K整除的子数组6 {
    //https://leetcode.cn/problems/subarray-sums-divisible-by-k/
    public int subarraysDivByK(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        int sum = 0, ret = 0;
        map.put(0,1); // sum = k,sum % k = 0,自己整的区间可以被k整除的是结果，自己整的就是结果，但往前减区间来得 是得不到的，得特判为就是结果地 就开始累积
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            int r = (sum % k + k) % k;
            // 找满足的前缀和
            ret += map.getOrDefault(r,0); // (sum - x) % k = 0 => sum % k = x % k，往前找 已存进哈希表里的 前缀和x % k的模 有多少个 等于 当前总区间前缀和sum % k的模
            // 存前缀和
            map.put(r, map.getOrDefault(r,0) + 1);
        }
        return ret;
    }
    public static void main(String[] args) {
        System.out.println(-5 % 3);
        System.out.println(5 % -3);
    }
}